package LeetCode.month02.day40;

import java.util.ArrayList;
import java.util.List;
import java.util.HashMap;
public class No30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        int wordlen = words[0].length();
        int windowlen = wordlen*words.length;
        HashMap<String,Integer> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            map.put(words[i],map.getOrDefault(words[i],0)+1);
        }

        for (int i = 0; i < wordlen; i++) {
            int overload = 0;
            HashMap<String,Integer> cnt = new HashMap<>();
            for (int j = i+wordlen; j <= s.length(); j+=wordlen) {
                String sub = s.substring(j-wordlen,j);
                if(cnt.getOrDefault(sub,0).equals(map.getOrDefault(sub,0))){
                    overload++;
                }
                cnt.put(sub,cnt.getOrDefault(sub,0)+1);
                int left = j-windowlen;
                if(left<0) continue;
                if(overload==0) res.add(left);
                String out = s.substring(left,left+wordlen);
                cnt.put(out,cnt.get(out)-1);
                if(cnt.get(out).equals(map.getOrDefault(out, 0))) overload--;
            }
        }
        return res;
    }
}
